/*
  魔法数字
  题目描述
    CxForce 对数字有他自己的偏好,
    在他看来, 一个数是美的, 当且仅当这个数字从前往后读和从后往前读是一样的,
    例如:
      232 是一个美的数字;
      而 233 则不是, 因为它从前往后读为 233, 从后往前读为 332, 两者不相等;
    对于不美的数字, CxForce 决定使用魔法将它们变成美的数字;
    对一个数施加魔法, 可以看作将这个数字加上它从后往前读的数字,
    例如:
      233 被施加魔法之后, 233 + 332 = 565, 经过一次魔法, 这个数字就变美了;
    请注意, CxForce 喜欢(会且仅会)在十进制下施法;

    由于 CxForce 学习数数的时候在开小差,
    所以他想请你告诉他一个任意进制的数字经过几次魔法之后可以变成十进制下美的数字，然后他就会开始施法。
    当然，如果需要施法的次数大于等于 10 次，CxForce 会觉得很烦，他就不会想施法了！
  输入
    一行两个字符串 a, b，表示需要施法的数字 a 是一个 b 进制数。
  输出
    记需要施法的次数为 answer，若 answer 小于 10 则输出 answer，
    否则输出 "It is a waste of magic."（不含引号，半角字符）。
  样例输入
    57 16
  样例输出
    4
  提示
    对于 20% 测试数据，b = 0
    对于另外 20% 测试数据， b = 2
    对于所有测试数据，0 ≤ a ≤ 2^20, 2 ≤ b ≤ 16
*/

#include <bits/stdc++.h>

using namespace std;

// 返回输入参数 n 对应的 10 进制数从后往前读得到的数
long long f(long long n) {
    long long x1 = 0;
    while (n > 0) {
        x1 = x1 * 10 + n % 10;
        n = n / 10;
    }

    return x1;
}

int main() {
    string s;
    int b;
    long long x = 0; // 10 进制数
    int j = 0;

    cin >> s >> b;

    // 将字符串 s 表示的 b 进制数转换成 10 进制数
    for (int i = s.size() - 1; i >= 0; i--) {
        int a;
        if (s[i] >= 'A' && s[i] <= 'F') {
            a = 10 + s[i] - 'A';
        } else if (s[i] >= 'a' && s[i] <= 'f') {
            a = 10 + s[i] - 'a';
        } else {
            a = s[i] - '0';
        }

        x = x + a * pow(b, j);
        j++;
    }

    for (int i = 1; i < 10; i++) {
        long long w = f(x);
        if (x == w) {
            cout << i - 1; // 注意: 由于循环变量 i 从 1 开始, 此处输出的次数需要减一。
            return 0;
        } else {
            x = x + w;
        }
    }
    cout << "It is a waste of magic.";

    return 0;
}